# -*- coding:utf-8 -*-

class TreeArray(object):
    '''
    Description:基于Python3实现一个简单的树状数组，支持基本的增删改查操作
    Author:Arcment
    Date:2022/3/6
    '''
    __length = 0
    __list_a, __list_c = [], []

    def __init__(self, array_list: list = []) -> None:
        self.__list_a = [0] * len(array_list)
        self.__list_c = [0] * len(array_list)
        self.__length = len(array_list)
        for i in range(self.__length):
            self.update(i, array_list[i])

    def __str__(self) -> str:
        return str(self.__list_a)

    def __eq__(self, __o: object) -> bool:
        if type(__o) != type(self):
            return False
        return self.__list_a == __o.__list_a

    def __len__(self) -> int:
        return self.__length

    @staticmethod
    def __lowbit(i: int) -> int:
        return i & (-i)

    def append(self, value: int) -> None:
        '''
        插入新元素
        '''
        self.__list_a.append(0)
        self.__list_c.append(0)
        self.__length += 1
        self.update(self.__length - 1, value)

    def update(self, index: int, value: int) -> None:
        '''
        更新数组中下标为index数据的数值，将值更新
        '''
        dif = value - self.__list_a[index]
        self.__list_a[index] = value
        while index < self.__length:
            self.__list_c[index] += dif
            index += self.__lowbit(index + 1)

    def add(self, index: int, dif: int) -> None:
        '''
        更新数组中下标为index数据的数值，使其值增加
        '''
        self.__list_a[index] += dif
        while index < self.__length:
            self.__list_c[index] += dif
            index += self.__lowbit(index + 1)

    def pop(self) -> None:
        '''
        删除数组中最后一个元素
        '''
        self.__list_a.pop()
        self.__list_c.pop()
        self.__length -= 1

    def query(self, index: int) -> int:
        '''
        查询数组第0到index-1项的和
        '''
        sum = 0
        if index >= self.__length or index < 0:
            assert False, 'Array out of bounds.'
        while index >= 0:
            sum += self.__list_c[index]
            index -= self.__lowbit(index + 1)
        return sum

    def clear(self) -> None:
        '''
        将数组中的元素清空
        '''
        self.__list_a.clear()
        self.__list_c.clear()
        self.__length = 0
